var roads = {};
function makeRoad(from, to, length)
{
	function addRoad(from, to)
	{
		if(!(from in roads))
			roads[from] = [];
		roads[from].push({to:to, distance:length});
	}
	addRoad(from, to);
	addRoad(to, from);
}
function makeRoads(start)
{
	for (var i = 1; i< arguments.length; i+=2)
	{
		makeRoad(start, arguments[i], arguments[i+1]);
	}
}
function BinaryHeap(scoreFunction){
  this.content = [];
  this.scoreFunction = scoreFunction;
}

BinaryHeap.prototype = {
  push: function(element) {
    // Add the new element to the end of the array.
    this.content.push(element);
    // Allow it to bubble up.
    this.bubbleUp(this.content.length - 1);
  },

  pop: function() {
    // Store the first element so we can return it later.
    var result = this.content[0];
    // Get the element at the end of the array.
    var end = this.content.pop();
    // If there are any elements left, put the end element at the
    // start, and let it sink down.
    if (this.content.length > 0) {
      this.content[0] = end;
      this.sinkDown(0);
    }
    return result;
  },

  remove: function(node) {
    var len = this.content.length;
    // To remove a value, we must search through the array to find
    // it.
    for (var i = 0; i < len; i++) {
      if (this.content[i] == node) {
        // When it is found, the process seen in 'pop' is repeated
        // to fill up the hole.
        var end = this.content.pop();
        if (i != len - 1) {
          this.content[i] = end;
          if (this.scoreFunction(end) < this.scoreFunction(node))
            this.bubbleUp(i);
          else
            this.sinkDown(i);
        }
        return;
      }
    }
    throw new Error("Node not found.");
  },

  size: function() {
    return this.content.length;
  },

  bubbleUp: function(n) {
    // Fetch the element that has to be moved.
    var element = this.content[n];
    // When at 0, an element can not go up any further.
    while (n > 0) {
      // Compute the parent element's index, and fetch it.
      var parentN = Math.floor((n + 1) / 2) - 1,
          parent = this.content[parentN];
      // Swap the elements if the parent is greater.
      if (this.scoreFunction(element) < this.scoreFunction(parent)) {
        this.content[parentN] = element;
        this.content[n] = parent;
        // Update 'n' to continue at the new position.
        n = parentN;
      }
      // Found a parent that is less, no need to move it further.
      else {
        break;
      }
    }
  },

  sinkDown: function(n) {
    // Look up the target element and its score.
    var length = this.content.length,
        element = this.content[n],
        elemScore = this.scoreFunction(element);

    while(true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) * 2, child1N = child2N - 1;
      // This is used to store the new position of the element,
      // if any.
      var swap = null;
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.content[child1N],
            child1Score = this.scoreFunction(child1);
        // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore)
          swap = child1N;
      }
      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[child2N],
            child2Score = this.scoreFunction(child2);
        if (child2Score < (swap == null ? elemScore : child1Score))
          swap = child2N;
      }

      // If the element needs to be moved, swap it, and continue.
      if (swap != null) {
        this.content[n] = this.content[swap];
        this.content[swap] = element;
        n = swap;
      }
      // Otherwise, we are done.
      else {
        break;
      }
    }
  }
};

makeRoads("Point Kiukiu", "Hanaiapa", 19,
          "Mt Feani", 15, "Taaoa", 15);
makeRoads("Airport", "Hanaiapa", 6, "Mt Feani", 5,
          "Atuona", 4, "Mt Ootua", 11);
makeRoads("Mt Temetiu", "Mt Feani", 8, "Taaoa", 4);
makeRoads("Atuona", "Taaoa", 3, "Hanakee pearl lodge", 1);
makeRoads("Cemetery", "Hanakee pearl lodge", 6, "Mt Ootua", 5);
makeRoads("Hanapaoa", "Mt Ootua", 3);
makeRoads("Puamua", "Mt Ootua", 13, "Point Teohotepapapa", 14);

var roadToAirport = roads["Airport"];

function identity(x)
{
	return x;
}

var heap = new BinaryHeap(identity);
forEach([2, 4, 5, 1, 6, 3], function(number){
	heap.push(number);
});

function estimatedDistance(pointA, pointB)
{
	var dx = Math.abs(pointA.x - pointB.x);
	var dy = Math.abs(pointA.y - pointB.y);
	if(dx > dy)
	{
		return (dx - dy) * 100 + dy * 141;
	}
	else
	{
		return (dy - dx) * 100 + dx * 141;
	}
}
function pointID(point)
{
	return point.x + "-" + point.y;
}

function makeReachedList()
{
	return {};
}

function storeReached(list, point, route)
{
	list[pointID(point)] = route;
}

function findReached(list, point)
{
	return list[pointID(point)];
}

function findRoute(from, to)
{
	var open = new BinaryHeap(routeScore);
	var reached = makeReachedList();
	
	function routeScore(route)	{
		if(route.score == undefined)		{
			route.score = estimatedDistance(route.point, to) + route.length;
		}
		return route.score;
	}
	
	function addOpenRoute(route)	{
		open.push(route);
		storeReached(reached, route.point, route);
	}	 
		
	addOpenRoute({point:from, length:0});
	
	while(open.size() > 0)
	{
		var route = open.pop();
		if(samePoint(route.point, to))		{
			return route;
		}
		
		forEach(possibleDirections(route.point), function(direction){
			var known = findReached(reached, direction);
			var newLength = route.length + 
							weightedDistance(route.point, direction);
			if( !known || known.length > newLength)			{
				if(known)				{
					open.remove(known);
				}
				addOpenRoute({point:direction,  //neighbors' position
				              from: route,
				              length:newLength});
			}
		});
	}
	return null;	
}


function point(x, y)
{
	return {x:x, y:y};
}

function addPoints(a, b)
{
	return point(a.x+b.x, a.y+b.y);
}
function samePoint(a, b)
{
	return a.x == b.x && a.y == b.y;
}
function possibleDirections(from)
{
	var mapSize = 20;
	function insideMap(point){
		return point.x >= 0 && point.x < mapSize &&
			   point.y >= 0 && point.y < mapSize;
	}
	
	var directions = [point(-1, 0), point(1, 0), point(0, -1),
					  point(0, 1), point(-1, -1), point(-1, 1),
					  point(1, 1), point(1, -1)];
	return filter(insideMap, map(partial(addPoints, from), directions));	
}
var points = possibleDirections(point(1, 2));

//alert(samePoint(addPoints(point(10, 10), point(4, -2)), point(14, 8)));

function weightedDistance(pointA, pointB)
{
	var heightDifference = heightAt(pointB) - heightAt(pointA);
	var climbFactor = (heightDifference < 0 ? 1:2);
	var flatDistance = (pointA.x == pointB.x || pointA.y == pointB.y ? 100: 141);
	return flatDistance + climbFactor * Math.abs(heightDifference);
}


function roadFrom(place)
{
	var found = roads[place];
	if( found == undefined)
	{	throw new Error("No place named '" + place + "' found.");}
	else 
	{	return found;}
}

//gambler's method
function gamblerPath(from, to)
{
	function randomInteger(below)
	{
		return Math.floor(Math.random() * below);
	}
	function randomDirection(from)
	{
		var options = roadFrom(from);
		return options[randomInteger(options.length)].to;
	}
	
	var path = [];
	while(true)
	{
		path.push(from);
		if(from == to)
		{break;}
		from = randomDirection(from);
	}
	return path;
}

function possibleRoutes(from, to) {
  function findRoutes(route) {
    function notVisited(road) {
      return !member(route.places, road.to);
    }
    function continueRoute(road) {
      return findRoutes({places: route.places.concat([road.to]),
                         length: route.length + road.distance});
    }

    var end = route.places[route.places.length - 1];
    if (end == to)
      return [route];
    else
      return flatten(map(continueRoute, filter(notVisited,
                                               roadFrom(end))));
  }
  return findRoutes({places: [from], length: 0});
}
function minimise(func, array)
{
	var minScore = null;
	var found = null;
	forEach(array, function(element){
		var score = func(element);
		if(minScore == null || minScore > score)
		{
			minScore = score;
			found = element;
		}
	});
	return found;
}
function getProperty(propName)
{
	return function(object){
		return object[propName];
	};
}

function shortestRoute(from, to)
{
	return minimise(getProperty("length"), possibleRoutes(from, to));
}

var route = possibleRoutes("Point Teohotepapapa", "Point Kiukiu");
var shortest_route = shortestRoute("Point Teohotepapapa", "Point Kiukiu");


var test = 1;

alert(test);

function map(func, array)
{
	var result = [];
	forEach(array, function(element){
		result.push(func(element));
	});
	return result;
}







/*

var op = { "===": function(a, b){return a ===b;},
			"!=": function(a, b){return a != b;}
         };
         */

var op = {
	"===": function(a, b){return a===b;},
	"-": function(a, b){return a-b;},
};
function member(array, value)
{
	
	return any(partial(function(a, b){return a===b;}, value), array);	
}

var found  = member(["Fear", "Loathing"], "Denial");
//alert(found);
found  = member(["Fear", "Loathing"], "Fear");
//alert(found);



function asArray(quasiArray, start)
{
	var result = [];
	for(var i = (start || 0); i<quasiArray.length; i++)
	{
		result.push(quasiArray[i]);
	}
	return result;
}

function filter(test, array)
{
	var result = [];
	forEach(array, function (element){
		if(test(element))
		{
			result.push(element);
		}
	});
	return result;
}
		
	
function flatten(arrays)
{
	var result = [];
	forEach(arrays, function(array){
		forEach(array, function(element){result.push(element);});
	});
	return result;
}
	

function partial(func)
{
	var fixedArgs = asArray(arguments, 1);
	return function()
	{
		return func.apply(null, fixedArgs.concat(asArray(arguments)));
	};
}
	        

var found = member(roads["Airport"], "Mt Ootua");
//alert(found);


function every(test, array)
{
	for(var i = 0; i<array.length; i++)
	{
		var found = test(array[i]);
		if(!found)
		{
			return found;
		}
	}
	return true;
}

function any(test, array)
{
	for(var i = 0; i<array.length; i++)
	{
		var found = test(array[i]);
		if( found)
		{
			return found;
		}
	}
	return false;
}

var Break = {toString:function(){return "Break";}};

function forEach(array, action)
{
	try {
		for(var i = 0; i<array.length; i++)
		{ 
			action(array[i]);
		}
	}
	catch ( exception)
	{
		if(exception != Break)
		{ throw exception;}
	}
}


